package leecode.字符串;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author wangxi03 created on 2021/5/31 1:09 下午
 * @version v1.0
 *
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 *
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 *
 * 本题直观的题解：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-powcai/
 */
public class LongestValidParentheses {
    public static void main(String[] args) {
        String s = ")()())";
        LongestValidParentheses obj = new LongestValidParentheses();
        System.out.println(obj.longestValidParentheses(s));
    }

    public int longestValidParentheses(String s) {
        if (s == null || s.length() <= 0) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    if (s.charAt(stack.peek()) == '(') {
                        list.add(stack.peek());
                        list.add(i);
                        stack.pop();
                    }
                }
            }
        }
        // 小到大进行排序
        list.sort((o1, o2) -> Integer.compare(o1, o2));
        int max = 0;
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            if (i > 0 && (list.get(i) == list.get(i - 1) + 1) ) {
                int cur = i - index + 1;
                if (cur > max) {
                    max = cur;
                }
            } else {
                index = i;
            }
        }
        return max;
    }
}
